package com.eddie.linkedlist;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class RemoveDuplicatesTest {
    public static void main(String[] args) {
        RemoveDuplicatesTest removeDuplicatesTest = new RemoveDuplicatesTest();

        Runtime r = Runtime.getRuntime();
        r.gc();//计算内存前先垃圾回收一次
        long start = System.currentTimeMillis();//开始Time
        long startMem = r.freeMemory(); // 开始Memory

        ListNode listNode = removeDuplicatesTest
                .partition(
                        new ListNode(1,
                                new ListNode(4,
                                        new ListNode(3
                                                , new ListNode(2
                                                , new ListNode(5, new ListNode(2))))))
                        , 3);
//        ListNode listNode = removeDuplicatesTest.deleteDuplicates(new ListNode(1, new ListNode(1, new ListNode(2,new ListNode(3,new ListNode(3))))));


        long endMem =r.freeMemory(); // 末尾Memory
        long end = System.currentTimeMillis();//末尾Time
        //输出
        System.out.println("用时消耗: "+String.valueOf(end - start)+"ms");
        System.out.println("内存消耗: "+String.valueOf((startMem- endMem)/1024)+"KB");
        while (listNode!=null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
    //给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
    //使用map映射解法，
    public ListNode deleteDuplicates(ListNode head) {
        Map<Integer,Integer> map = new HashMap<>();
        ListNode result = new ListNode(0,head);
        ListNode cur = result;
        while(cur.next != null) {
            if(map.containsKey(cur.next.val)) {
                cur.next = cur.next.next;
            }else {
                map.put(cur.next.val,0);
                cur = cur.next;
            }
        }

        LinkedList<String> strings = new LinkedList<>();

        return result.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode cur = new ListNode(0);
        ListNode ch = cur;
        for (int i = 0; i < lists.length; i++) {
            while (lists[i]!=null) {
                int val = lists[i].val;

                lists[i] = lists[i].next;

            }
        }
         return null;
    }

    /**
     *
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        ListNode l  = new ListNode(0);
        ListNode lh = l;
        ListNode r = new ListNode(0);
        ListNode rh = r;
        while (head!=null) {
            if(head.val<x) {
                l.next = head;
                l = l.next;
            }else {
                r.next = head;
                r = r.next;
            }
            head = head.next;
        }
        r.next = null;
        l.next = rh.next;
        return lh.next;
    }

}
